#include <stdio.h>
#include <stdlib.h>

//顶点的最大个数
#define MAX_VERtEX_NUM 20
//表示顶点之间的关系的变量类型
#define VRType int
//存储弧或者边额外信息的指针变量类型
#define InfoType char
//图中顶点的数据类型
#define VertexType int
//定义bool型常量
typedef enum {false,true} bool;
//设置全局数组，记录标记顶点是否被访问过
bool visited[MAX_VERtEX_NUM];

typedef struct Queue {
    VertexType data;
    struct Queue * next;
}QUEUE;

typedef struct {
    //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值
    VRType adj;
    //弧或边额外含有的信息指针
    InfoType * info;
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    //存储图中顶点数据
    VertexType vexs[MAX_VERtEX_NUM];
    //二维数组，记录顶点之间的关系
    AdjMatrix arcs;
    //记录图的顶点数和弧（边）数
    int vexnum, arcnum;
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for(; i < G->vexnum; i++) {
        if(G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if(i > G->vexnum) {
        printf("not found\n");
        return -1;
    }
    return i;
}

//构造无向图
void CreateDN1(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    G->vexnum = 8;
    G->arcnum = 9;
    //初始化图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        G->vexs[i] = i+1;
    }
    //在二维数组中添加弧的数据
    /*
    {
          v1 v2 v3 v4 v5 v6 v7 v8
    v1    0  1  1  0  0  0  0  0
    v2    1  0  0  1  1  0  0  0
    v3    1  0  0  0  0  1  1  0
    v4    0  1  0  0  0  0  0  1
    v5    0  1  0  0  0  0  0  1
    v6    0  0  1  0  0  0  1  0
    v7    0  0  1  0  0  1  0  0
    v8    0  0  0  1  1  0  0  0
    }
    */
   for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
   }
   //无向图的二阶矩阵沿主对角线对称
   //V1-V2
   G->arcs[0][1].adj = 1;
   G->arcs[1][0].adj = 1;
   //V1-V3
   G->arcs[0][2].adj = 1;
   G->arcs[2][0].adj = 1;
   //V2-V4
   G->arcs[1][3].adj = 1;
   G->arcs[3][1].adj = 1;
   //V2-V5
   G->arcs[1][4].adj = 1;
   G->arcs[4][1].adj = 1;
   //V3-V6
   G->arcs[2][5].adj = 1;
   G->arcs[5][2].adj = 1;
   //V3-V7
   G->arcs[2][6].adj = 1;
   G->arcs[6][2].adj = 1;
   //V4-V8
   G->arcs[3][7].adj = 1;
   G->arcs[7][3].adj = 1;
   //V5-V8
   G->arcs[4][7].adj = 1;
   G->arcs[7][4].adj = 1;
   //V6-V7
   G->arcs[5][6].adj = 1;
   G->arcs[6][5].adj = 1;
}

void CreateDN(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //输入图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    //初始化图
    for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    //查找元素位置，记录弧
    for(int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if(n == -1 || m == -1) {
            printf("not found\n");
            return;
        }
        //无向图的二阶矩阵沿主对角线对称
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
}
//第一个相邻顶点
int FirstAdjVex(MGraph G, int v) {
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}
//下一个相邻顶点
int NextAdjVex(MGraph G, int v, int w) {
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for(int i = w+1; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}
//操作顶点的函数
void visitVex(MGraph G, int v) {
    printf("%d ", G.vexs[v]);
}
//初始化队列
void InitQueue(QUEUE ** Q) {
    (*Q) = (QUEUE *)malloc(sizeof(QUEUE));
    (*Q)->next = NULL;
}
//顶点元素v进队列
void EnQueue(QUEUE ** Q, VertexType v) {
    QUEUE * element = (QUEUE *)malloc(sizeof(QUEUE));
    element->data = v;
    element->next = NULL;
    QUEUE * temp = (*Q);
    while (temp->next != NULL)
    {
        /* code */
        temp = temp->next;
    }
    temp->next = element;
}
//队头元素出队列
void DeQueue(QUEUE ** Q, int * u) {
    (*u) = (*Q)->next->data;
    (*Q)->next = (*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(QUEUE * Q) {
    if(Q->next == NULL) {
        return true;
    }
    return false;
}
//广度优先搜索
void BFSTraverse(MGraph G) {
    int v;
    //将用做标记的visit数组初始化为false
    for(int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    //对于每个标记为false的顶点调用深度优先搜索函数
    QUEUE * Q;
    InitQueue(&Q);
    for(v = 0; v < G.vexnum; v++) {
        if(!visited[v]) {
            visited[v] = true;
            visitVex(G, v);
            EnQueue(&Q, G.vexs[v]);
            while (!QueueEmpty(Q))
            {
                /* code */
                int u;
                DeQueue(&Q, &u);
                u = LocateVex(&G, u);
                for(int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {
                    if (!visited[w])
                    {
                        /* code */
                        visited[w] = true;
                        visitVex(G, w);
                        EnQueue(&Q, G.vexs[w]);
                    }
                }
            }
        }
    }
}

void PrintGraph(MGraph G) {
    for(int i = 0 ; i < G.vexnum; i++) {
        for(int j = 0; j < G.vexnum; j++) {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    MGraph G;
    //调用创建函数，传入地址参数
    CreateDN1(&G);
    //调用创建函数，传入地址参数
    //CreateGraph(&G);
    //输出图的二阶矩阵
    PrintGraph(G);
    printf("\n");
    //广度优先搜索图
    BFSTraverse(G);
    return 0;
}